package de.hska.master.algo.quickHull;

import java.util.ArrayList;
import java.util.List;

import de.hska.master.model.Model;
import de.hska.master.model.Point;
import de.hska.master.support.Geometry;

/**
 * Class which implements the merge hull algorithm. Source is:
 * http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html
 * 
 * @author Claudio
 * 
 */

public class QuickHullAlgorithm {

	private Model model = null;
	private Geometry geometry = null;
	private List<Point> convexHull;
	private List<Point> points = null;

	/**
	 * Constructor for the merge Hull Algorithm. Initializes the model and the Geometry class.
	 * 
	 * @param model
	 */
	public QuickHullAlgorithm(Model model) {
		super();
		this.model = model;
		this.geometry = new Geometry();
	}

	/**
	 * See here: http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html
	 * 
	 * @return convex hull of list {@link QuickHullAlgorithm#calculations}
	 * @throws InterruptedException
	 */
	public List<Point> runAlgorithm() throws InterruptedException {
		this.points = model.getPointsAsList();
		this.convexHull = new ArrayList<Point>(points.size());

		this.constructConvexHull();

		return convexHull;
	}

	private void constructConvexHull() {
		quickHull();
	}

	private void quickHull() {

		int leftMostPointIndex = geometry.getLeftMostPoint(points);
		int rightMostPointIndex = geometry.getRightMostPoint(points);

		Point leftMostPoint = points.get(leftMostPointIndex);
		Point rightMostPoint = points.get(rightMostPointIndex);

		/**
		 * Split sides
		 */
		List<Point> s1 = new ArrayList<Point>();
		List<Point> s2 = new ArrayList<Point>();

		s1 = geometry.getPointsRightOfLine(points, leftMostPoint, rightMostPoint);
		s2 = geometry.getPointsRightOfLine(points, rightMostPoint, leftMostPoint);

		/**
		 * Call algo for every side
		 */

		convexHull.add(leftMostPoint);
		findHull(s1, leftMostPoint, rightMostPoint);
		convexHull.add(rightMostPoint);
		findHull(s2, rightMostPoint, leftMostPoint);
	}

	/**
	 * 
	 * @param points
	 *            aka Sk (in terminology of pseudo-code) represents the set of points to execute algorithm on
	 * @param lineStart
	 *            aka P (in terminology of pseudo-code) represents the start of the line segment
	 * @param lineEnd
	 *            aka Q (in terminology of pseudo-code) represents the end of the line segment
	 */
	private void findHull(List<Point> points, Point lineStart, Point lineEnd) {
		// If Sk has no point,
		// then return
		if (points.size() == 0) {
			return;
		}

		// From the given set of points in Sk, find farthest point, say C, from segment PQ
		Point farestPoint = geometry.getFarestPointToLine(points, lineStart, lineEnd);// aka C (in terminology of
																						// pseudo-code)
		// Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2
		// where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented
		// line from P to C, and S2 are points on the right side of the oriented line from C to Q.
		List<Point> s1 = geometry.getPointsRightOfLine(points, lineStart, farestPoint);
		List<Point> s2 = geometry.getPointsRightOfLine(points, farestPoint, lineEnd);

		// FindHull(S1, P, C)
		findHull(s1, lineStart, farestPoint);
		// Add point C to convex hull at the location between P and Q
		convexHull.add(farestPoint);
        // FindHull(S2, C, Q)
		findHull(s2, farestPoint, lineEnd);
	}
}
